#include <stdio.h>
#include <stdlib.h>
#include <stack>

struct TreeNode {
  int data;
  TreeNode *left, *right;
};

typedef TreeNode* Tree;

class InorderTraversal {
  public:
    InorderTraversal(TreeNode *t):t_(t), cursor_(t) {}
    /**
     * Returns NULL at the end of the traversal
     *
     **/
    TreeNode* next() {
      while (cursor_) {
        s_.push(cursor_);
        cursor_ = cursor_->left;
      }

      if (!s_.empty()) {
        TreeNode* ret = s_.top();
        s_.pop();
        cursor_ = ret->right;
        return ret;
      }

      return NULL;
    }

    void reset() {
      cursor_ = t_;
      s_ = std::stack<TreeNode*>();
    }

  private:
    Tree t_;
    TreeNode* cursor_;
    std::stack<TreeNode*> s_;  
};

Tree insert(Tree t, int el) {

  if (t == NULL) {
    t = (TreeNode *)calloc(sizeof(TreeNode), 1); 
    t->data = el;
  } else {
    if(el <= t->data) {
      if(t->left) {
          insert(t->left, el);
      } else {
          t->left = (TreeNode *)calloc(sizeof(TreeNode), 1); 
          t->left->data = el;
      }
    } else {
      if(t->right) {
          insert(t->right, el);
      } else {
          t->right = (TreeNode *)calloc(sizeof(TreeNode), 1); 
          t->right->data = el;
      }
    }
  }

  return t;
}


int main() {
  int i;
  Tree t1  = NULL;
  Tree t2  = NULL;
  
  for (i = 1; i <= 3; i++) {
    t1 = insert(t1, i);
  }

  for (i = 4; i <= 6; i++) {
    t2 = insert(t2, i);
  }

  InorderTraversal s1(t1);
  InorderTraversal s2(t2);

  TreeNode *n1 = s1.next(), *n2 = s2.next(); 

  while (n1 && n2) {
    if (n1->data < n2->data) {
      printf("%d ", n1->data);
      n1 = s1.next();
    } else {
      printf("%d ", n2->data);
      n2 = s2.next();
    }
  }

  while (n1) {
    printf("%d ", n1->data);
    n1 = s1.next();
  }

  while (n2) {
    printf("%d ", n2->data);
    n2 = s2.next();
  }

  printf("\n");
}
